package offer.day27;

public class No43NumberOf1Between1AndN {
    /*
     * 面试题43：1—n整数中1出现的次数
     * 题目:输入一个整数n,求1-n这n个整数中的十进制表示中1出现的次数
     * 例如：输入12，1-12这些整数中包含1 的数字有1、10、11、12  1一共出现了5次（11算作2次）
     * （求出任意非负整数区间的1出现的个数）
     *
     * 思路：总结规律发现：   时间复杂度O(k)    k为位数
     * 当前位的值 = 0时，1出现的次数为： 高位值*当前位位数
     * 当前位的值 = 1时，1出现的次数为： 高位值*当前位位数 + 当前位数值 % 当前位位数 + 1
     * 当前位的值 > 1时，1出现的次数为： （高位值 + 1）*当前位位数
     *
     * 例如：n = 21305  每一位出现1的情况统计
     * 万位(>1)：(21305 / 100000 + 1) * 10000 = 10000次
     * 千位(=1)：(21305 / 10000 ) * 1000 + 21305 % 1000 + 1 = 2306次
     * 百位(>1)：(21305 / 1000 + 1) * 100 = 2200次
     * 十位(=0)：(21305 / 100) * 10 = 2130次
     * 个位(>1)：(21305 /10 + 1) * 1 = 2131次
     * */
    public static void main(String[] args) {
        No43NumberOf1Between1AndN number = new No43NumberOf1Between1AndN();
        int n = 21305;
        System.out.println("1出现的次数为：" + number.NumberOf1Between1AndN(n));
    }

    private int NumberOf1Between1AndN(int n) {
        if(n<=0) return 0;
        int sum=0;
        for(int k=1;n/k>0;k*=10){
            int mod=n/k%10;
            if(mod>1){
                sum+=((n/(k*10))+1)*k;
            }else if(mod==1){
                sum+=(n/(k*10))*k+n%k+1;
            }else{
                sum+=(n/(k*10))*k;
            }
        }
        return sum;
    }
}
